package Hot_100;

public class T19_removeNthFromEnd {

// 双指针之快慢指针:
//    先让start指针向右移动n步;而end保持不变;此时start和end的距离为n，然后让start和end都继续向右移动，
//    直到start到达链表最后一个结点，此时倒数第n个节点实际就是end指针的下一个结点，将其删除即可
//     该算法只需要遍历一次链表就能得到答案
    public ListNode removeNthFromEnd_1(ListNode head, int n) {
        ListNode pre = new ListNode();
        pre.next = head;
        ListNode start,end;
        start = end = pre;
        for (int i = 0; i < n; i++) {   //start指针先向前移动n步
            start=start.next;
        }
        while (start.next != null) {
            start = start.next;
            end = end.next;
        }

        end.next=end.next.next;
        return pre.next;
    }
}
